// cur节点是数值在[p, q]区间中则说明该节点cur就是最近公共祖先了。

// 和236不同，普通二叉树求最近公共祖先需要使用回溯，从底向上来查找，
// 二叉搜索树就不用了，因为搜索树有序（相当于自带方向），那么只要从上向下遍历就可以了。
// 那么我们可以采用前序遍历（其实这里没有中节点的处理逻辑，遍历顺序无所谓了）。
class Solution {
 private:
  TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
    if (cur == NULL) return cur;
    // 中，无处理逻辑
    if (cur->val > p->val && cur->val > q->val) {  // 左
      TreeNode* left = traversal(cur->left, p, q);
      if (left != NULL) {
        return left;
      }
    }

    if (cur->val < p->val && cur->val < q->val) {  // 右
      TreeNode* right = traversal(cur->right, p, q);
      if (right != NULL) {
        return right;
      }
    }
    return cur;
  }

 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    return traversal(root, p, q);
  }
};
// TODO: 自己写下